package day013;

import java.util.Scanner;

public class NColor {
    static final int MX = 50;
    static int[] x = new int[MX];
    static int[][] map = new int[MX][MX];
    static int sum = 0;
    static int n, m, edge;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入节点数：");
        n = scanner.nextInt();
        System.out.println("输入颜色数：");
        m = scanner.nextInt();
        System.out.println("输入无向图的邻接矩阵：");
        System.out.println("请输入边数：");
        edge = scanner.nextInt();
        int u, v;
        System.out.println("请依次输入有边相连的两个结点u和v，用空格分开：");
        for (int i = 1; i <= edge; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            map[u][v] = map[v][u] = 1;
        }

        backTrack(1);                                                //从第1层开始搜索
    }

    private static void backTrack(int t) {
        if (t > n) {
            sum++;
            System.out.print("第" + sum + "种方案：");
            for (int i = 1; i <= n; i++)                                    //输出该着色方案
                System.out.print(x[i] + " ");
            System.out.println();
        } else {
            for (int i = 1; i <= m; i++) {
                x[t] = i;
                if (OK(t)) {
                    backTrack(t + 1);
                }
            }
        }
    }

    public static boolean OK(int t) {
        for (int j = 1; j < t; j++) {                                       //依次判断前t-1个结点
            if (map[t][j] == 1) {                                       //判断t和j是否相邻
                if (x[j] == x[t])                                       //判断着色是否相同
                    return false;                                    //有相同着色则返回false
            }
        }
        return true;
    }
}
